#include "main/utils.h"
using namespace std;

int maxGiftsValue(const vector<vector<int>> &gifts) {
  int rows = gifts.size();
  int cols = gifts[0].size();
  vector<int> max_gifts(cols, 0);
  for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < cols; ++j) {
      if (j > 0) {
        max_gifts[j] = max(max_gifts[j], max_gifts[j - 1]) + gifts[i][j];
      } else {
        max_gifts[j] = max_gifts[j] + gifts[i][j];
      }
    }
  }
  return max_gifts[cols - 1];
}

int main() {
  vector<vector<int>> gifts = {{1, 10, 3, 8},
                               {12, 2, 9, 6},
                               {5, 7, 4, 11},
                               {3, 7, 16, 5}};
  int ret = maxGiftsValue(gifts);
  cout << "The maximum gifts is: " << ret << endl;
}
